1. Field of the Invention
This invention relates to computer network technology, and more particularly, to a method and system for packet classification on a network system, such as Internet or an intranet/extranet system, for applications such as firewalls, policy-based routing, and network service differentiations.
2. Description of Related Art
Packet classification is an important function of network systems for applications such as firewalls and intrusion detection, policy-based routing, and network service differentiations, for use to identify the attributes of all incoming packets based on their headers. When a networking device, such as an enterprise-class server or router, receives an incoming packet, the first step is to determine the type of the packet, such as what protocol is being used by the packet, what ToS (Type of Service) or QoS (Quality of Service) is to be assigned to the packet, the source and destination of the packet (which might be used to indicate, for example, whether the packet is coming from a malignant source), to name just a few.
In actual implementation, packet classification is realized by using a user-predefined rule database which specifies the mapping of predefined field values in the packet header to a set of rules, each rule representing a particular type of action or service that is to be performed on the packet. For example, if the source IP address of an incoming packet is matched to a rule that specifies an unauthorized IP address, the action to be performed on the incoming packet might be to discard the packet or to trace back to its originating source.
Typically, the total number of rules in a rule database might be in the range from several dozens to several thousands. Therefore, the hardware/software implementation of packet classification typically requires a huge amount of memory space for storage of the rule database and also requires a significant amount of access time to search through the rule database for matched rules.
In view of the aforementioned problem, it has been a research effort in the computer network industry for solutions that implement packet classification with reduced memory space and enhanced access speed. For example, the technical paper “SCALABLE PACKET CLASSIFICATION USING BIT VECTOR AGGREGATING AND FOLDING” by Li et al; “SCALABLE PACKET CLASSIFICATION” by Baboescu et al; and “SCALABLE AND PARALLEL AGGREGATED BIT VECTOR PACKET CLASSIFICATION USING PREFIX COMPUTATION MODEL”; to name a few. These papers teach the use of aggregated bit vectors (ABV) and folded bit vectors (FBV), which are a compacted form of the so-called Lucent Bit Vector, to help reduce memory space and enhance access speed during the operation of packet classification.
One drawback to the above-mentioned ABV/FBV scheme for packet classification, however, is that it requires the use of a trie-based data structure for mapping the packet header information to corresponding ABV/FBV values, and the use of the trie-based data structure still requires a significant amount of memory space for storage.